#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int x_mv[4] = {1, 0, -1, 0};
        int y_mv[4] = {0, 1, 0, -1};
        vector<int> ans;
        int size = matrix.size()*matrix[0].size();
        int cnt = 0;
        int x = 0;
        int y = 0;
        for(int i=0; i<size; ++i){
            ans.emplace_back(matrix[y][x]);
            if(i==size-1) break;
            matrix[y][x] = 10000;
            int new_x = x+x_mv[cnt%4];
            int new_y = y+y_mv[cnt%4];
            while(new_x<0 || new_y<0 
                || new_x>=matrix[0].size() || new_y>=matrix.size()
                || matrix[new_y][new_x]==10000){
                    ++cnt;
                    new_x = x+x_mv[cnt%4];
                    new_y = y+y_mv[cnt%4];
            }
            x = new_x;
            y = new_y;
        }
        return ans;
    }
};

int main(){

}